Sakura Tears training 5 题解

A - A Wide, Wide Graph

Question

给定一颗 $n$ 个顶点的树，给定一个固定的整数 $k$ ，定义图 $G_{k}$ 为 $n$ 个顶点的图， $u, v$ 之间存在连边当且仅当在树上的距离 $\geq k$ ，对于每个 $k$ 从 $1$ 到 $n$ ，求图 $G_{k}$ 中的连通分量树

Solution

如果设树的直径为 $d$ ，如果 $d > k$ ，那么图肯定是 $n$ 个孤立的点

否则直径的端点肯定在一个连通块上的

定义树上节点 $x$ 到最远的树的端点距离为 $d i s [x]$ 如果 $d i s [x] > k$ 那么 $x$ 也和两端在同一个连通块里面的

由于 $k$ 递增，所以可以 $O (n)$ 求答案

Code

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n; cin >> n;
    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    function<void(int, int, vector<int>&)> dfs = [&](int u, int f, vector<int> &d) {
        d[u] = d[f] + 1;
        for (int v : g[u]) if (v != f) dfs(v, u, d);
    };

    vector<int> d(n + 1, 0), d1(n + 1, 0), d2(n + 1, 0);
    dfs(1, 0, d);
    int u = max_element(d.begin() + 1, d.end()) - (d.begin() + 1) + 1;
    dfs(u, 0, d1);
    int v = max_element(d1.begin() + 1, d1.end()) - (d1.begin() + 1) + 1;
    dfs(v, 0, d2);
    for (int i = 1; i <= n; i++) d[i] = max(d1[i], d2[i]);
    int mxd = d1[v];
    sort(d.begin() + 1, d.end());
    int pos = 1;
    for (int i = 1; i <= n; i++) {
        if (i >= mxd) cout << n << ' ';
        else {
            while (pos <= n && d[pos] <= i) pos += 1;
            cout << pos << ' ';
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    while (T--) solve();
    return 0;
}

B - Not Adding

Question

CF1627D Not Adding

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    freopen ("B.in", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    int m = *max_element(a.begin() + 1, a.end());
    vector<int> cnt(m + 1, 0);
    for (auto x : a) cnt[x]++;
    int num = 0;
    for (int i = m; i >= 1; i--) {
        int g = 0;
        for (int j = i; j <= m; j += i) {
            if (cnt[j])
                g = __gcd(g, j);
        }
        if (g == i) {
            if (cnt[i] == 0) {
                num += 1;
                cnt[i] = 1;
            }
        }
    }
    cout << num << endl;
    return 0;
}

C - String Deletion

Question

CF1430D String Deletion

你有一个由 $n$ 个字符组成的 01 字符串 $s$

你可以对字符串进行操作，每个操作包括两个步骤：

选择一个整数 $i$ ，然后删除字符 $s_{i}$
如果字符串 $s$ 不为空，删除由相同字符组成的最大长度前缀

当字符串 $s$ 变为空时，结束操作。你能执行的最大操作次数是多少？

Solution

贪心，显然，要删除长度 $> 1$ 的连续字符中的其中 $1$ 个

我们从前往后看，如果有 $> 1$ 的，就操作它，直到它被操作 $2$ 删去或者长度 $= 1$

具体实现可以用双指针或者堆来实现

Code

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

void solve() {
    int n; cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        char ch; cin >> ch;
        a[i] = ch - '0';
    }
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    int cnt_1 = 0;
    for (int i = 1; i <= n;) {
        int j = i;
        while (j <= n && a[j] == a[i]) j++;
        if (j - i > 1) pq.push({i, j - i});
        i = j;
    }
    int ans = 0, pos = 1;
    

    while (pos <= n) {

        auto get_pair = [&] () {
            while (!pq.empty() && pq.top().first < pos) pq.pop();
            if (pq.empty()) return pii(-1, -1);
            return pq.top();
        };

        auto [id, len] = get_pair();
        if (id == -1) {
            int ans2 = 0;
            for (int i = pos; i <= n; i) {
                int j = i;
                while (j <= n && a[j] == a[i]) j++;
                ans2 += 1;
                i = j;
            }
            cout << ans + (ans2 + 1) / 2 << '\n';
            return ;
        }
        else {
            int j = pos;
            while (j <= n && a[j] == a[pos]) j++;
            pos = j;
            ans += 1;
            pq.pop();
            if (len - 1 > 1) pq.push({id, len - 1});
        }
    }
    cout << ans << '\n';
}

int main() {
    freopen ("C.in", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

D - Another Array Problem

Question

CF1763C Another Array Problem

给定一个数组 $a$ ，可以进行无数次操作：

选择 $i, j, i < j$ ，用 $| a_{i} - a_{j} |$ 替换所有 $i \leq k \leq j$ 的所有 $a_{k}$

求最后 $a$ 的和的最大值

Solution

一股 $C F$ 的味道的题

考虑到如果操作两次相同的 $i, j$ 中间的数会变成 $0$

也就说， $n > 4$ 的时候，可以全部变成序列中的最大的数

然后考虑 $n = 3$

可以全部变成 $a_{1}, a_{3}, | a_{2} - a_{1} |, | a_{3} - a_{2} |$
或者不操作

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n; cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (n == 2) {
        cout << max({2 * abs(a[1] - a[2]), a[1] + a[2]}) << '\n';
        return ;
    }
    if (n == 3) {
        cout << max({3 * a[1], 3 * a[3], 3 * abs(a[1] - a[2]), 3 * abs(a[2] - a[3]), a[1] + a[2] + a[3]}) << '\n';
    }
    else 
        cout << n * (*max_element(a.begin() + 1, a.end())) << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

E - XOR-gun

Question

CF1415D XOR-gun

Solution

诈骗题的味道

考虑到如果三个数的最高位都一样，那么把后两个数异或起来肯定小于第三个

所以 $n > 60$ 时，答案肯定时 $1$

对于小于 $60$ 的部分， $O (n^{3})$ 的暴力即可

Code

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int main() {
    freopen ("E.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    if (n > 60) {
        cout << "1\n";
        return 0;
    }
    vector<int> a(n + 1), sum(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] ^ a[i];
    }
    int ans = INF;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            for (int k = j; k <= n; k++) {
                if ((sum[i - 1] ^ sum[j - 1]) > (sum[j - 1] ^ sum[k])) {
                    ans = min(ans, k - i - 1);
                }
            }
        }
    }
    if (ans == INF) cout << "-1\n";
    else cout << ans << '\n';
}

F - Restorer Distance

Quesiton

CF1355E Restorer Distance

Solution

显然， $M = min (M, A + R)$

然后发现答案是可三分的

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    freopen ("F.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int N, A, R ,M; cin >> N >> A >> R >> M;
    vector<int> h(N + 1);
    for (int i = 1; i <= N; i++) cin >> h[i];
    M = min(M, A + R);
    
    auto check = [&] (int mid) -> ll{
        ll sum1 = 0, sum2 = 0;
        for (int i = 1; i <= N; i++) {
            if (h[i] < mid) sum1 += mid - h[i];
            else sum2 += h[i] - mid;
        }
        ll sum = min(sum1, sum2);
        sum1 -= sum; sum2 -= sum;
        return sum1 * A + sum2 * R + sum * M;
    };

    int l = 0, r = 1e9;
    while (l < r) {
        int lmid = l + (r - l) / 3, rmid = r - (r - l) / 3;
        if (check(lmid) < check(rmid)) r = rmid - 1;
        else l = lmid + 1;
    }
    cout << check(l) << '\n';
    return 0;
}

G - Earn or Unlock

Question

CF1854B Earn or Unlock

安德烈正在玩游戏 Tanto Cuore。

他有一副 $n$ 张牌，从顶部到底部的值分别为 $a_{1}, \dots, a_{n}$ 。每张牌可以是锁定的或未锁定的。初始时，只有最顶部的牌是未锁定的。

游戏进行按回合进行。每回合，安德烈选择一张未锁定的牌 — 牌上写着的值为 $v$ — 并执行以下两种操作中的一种：

解锁牌堆顶的前 $v$ 张锁定牌。如果牌堆中锁定的牌少于 $v$ 张，则解锁全部锁定的牌。
赚取 $v$ 点胜利点数。

在执行完操作后，无论哪种情况，他都要从牌堆中移除这张牌。

游戏在牌堆中剩余的所有牌都被锁定时结束，或者牌堆中没有更多的牌时结束。

安德烈可以获得的最大胜利点数是多少？

Solution

我们发现了一个事实，如果我选了前 $x$ 张牌，那么有等式 $s + x - 1 = \sum_{i = 1}^{x} a_{i}$

变换一下得到 $s = \sum_{i = 1}^{x} a_{i} - x + 1$

所以就转化成了一个类似于前缀和的式子

然后就看能不能走到 $x$ ，很显然有 01 背包，定义 $d p [i [j]$ 表示前 $i$ 个 $a [i]$ 是否能到达 $j$

d p [i] [j] \lor = d p [i - 1] [j << a [i]]

位运算可以用 bitset 优化， $i$ 又只和 $i - 1$ 有关，所以可以用滚动数组优化

在使用完 $d p [i]$ 后，应该把 $d p [i] [i]$ 置为 $0$ ，因为对于前 $i$ 个来说，第 $i$ 个卡牌必须用作赚取点数

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    freopen ("G.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<ll> a(2 * n + 1, 0), sum(2 * n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= 2 * n; i++) sum[i] = sum[i - 1] + a[i];
    bitset<200005> dp;
    dp[1] = 1;
    ll ans = 0;
    for (int i = 1; i <= 2 * n; i++) {
        dp |= dp << a[i];
        if (dp[i]) {
            ans = max(ans, sum[i] - i + 1);
            dp[i] = 0;
        }
    }
    cout << ans << '\n';
    return 0;
}